//题目:
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
    int ret=0;
    int arr[20001]={0};//备忘录
public:
    //计算以pos位置为起始的最长递增子序列
    int dfs(vector<int>& nums,int pos,int prev)
    {
        //只要能进这个函数，就说明pos是合法的

        if(arr[pos]!=0)return arr[pos];//记忆功能，可以省去大量的、重读的计算

        int ret=1;//这个1表示nums[pos]自己的长度
        for(int i=pos+1;i<nums.size();i++)
        {
            if(nums[i]>prev)
            {
                ret=max(ret,1+dfs(nums,i,nums[i]));//dfs表示nums[pos]后面符合题意的数组长度
            }
        }

        arr[pos]=ret;//记录以nums[pos]为起始位置的最长递增子序列长度
        return ret;
    }
    int lengthOfLIS(vector<int>& nums) 
    {
        //法一：记忆化搜索
        // int ret=0;
        // for(int i=0;i<nums.size();i++)
        //     ret=max(ret,dfs(nums,i,nums[i]));
        // return ret;

        //法二：动态规划
        //1.创建dp表————dp[i]表示以nums[i]为起点，到数组最后一个元素的“最长递增子序列长度”
        vector<int> dp(nums.size());
        //2.初始化
        dp[nums.size()-1]=1;
        //3.填表————动态转移方程：dp[i]=nums[i]>nums[i+1]?dp[i+1]+1:就跟nums[i+2]比，直到比到最后一个元素
        for(int i=nums.size()-2;i>=0;i--)
        {
            dp[i]=1;//nums[i]自己的长度
            int max_len=0;
            for(int j=i+1;j<nums.size();j++)
                if(nums[i]<nums[j])
                    max_len=max(max_len,dp[j]);//后续最大递增子序列的长度
            dp[i]+=max_len;
        }
        //4.确定返回值
        int ret=1;
        for(int i=0;i<nums.size();i++)
            ret=max(ret,dp[i]);
        return ret;
    }
};